Crate recursive

Rust has a problematic relationship with recursive functions, because functions that recurse deeply can overflow the stack, crashing your program. This crate makes it easy to remedy this problem by marking (indirectly) recursive functions as such:

use recursive::recursive;

#[recursive]
fn sum(nums: &[u64]) -> u64 {
    if let Some((head, tail)) = nums.split_first() {
        head + sum(tail)
    } else {
        0
    }
}

The way this prevents stack overflows is by checking the size of the remaining stack at the start of each call to your function. If this size is under a boundary set by set_minimum_stack_size (by default 128 KiB), a new stack is allocated and execution continues on that stack. This new stack’s size is set using set_stack_allocation_size, which is 2 MiB by default.

This crate works by wrapping your function body in a call to stacker::maybe_grow. If this crate is not flexible enough for your needs consider using stacker directly yourself.

What are the downsides?

This crate is not zero cost, but it is also not limited to simple tail recursion or direct recursion. However, in most cases the stack size test is very fast and almost always succeeds without needing to allocate. If your recursive algorithm is very performance-sensitive I would suggest rewriting it to an iterative version regardless.

This crate only supports those platforms that stacker supports. The Rust compiler itself uses stacker, so the platform you’re compiling on should always be fine, but for more obscure targets see its documentation.

Which functions should I mark as #[recursive]?

Any function that directly calls itself should be marked as #[recursive], unless you know for certain that the stack is sufficiently large for any inputs that function will be called with. If you are feeding untrusted input into a recursive function you should always mark it as #[recursive].

It is not necessary to mark every single function that can indirectly recurse as #[recursive]. As long as every possible cycle of function calls includes at least one function marked #[recursive] you will be protected against stack overflows due to recursion.

Functions

• get_minimum_stack_size
  Returns the value set by set_minimum_stack_size.
• get_stack_allocation_size
  Returns the value set by set_stack_allocation_size.
• set_minimum_stack_size
  This sets the minimum stack size that recursive requires.
• set_stack_allocation_size
  When a new stack gets allocated it will get allocated with this size.

Attribute Macros

• recursive
  Marks a function to use an automatically growing segmented stack.